from typing import List


def partition(nums: List, low: int, high: int):
    i = low - 1  # 最小元素索引
    pivot = nums[high]

    for j in range(low, high):

        # 当前元素小于或等于 pivot
        if nums[j] <= pivot:
            i = i + 1
            nums[i], nums[j] = nums[j], nums[i]

    nums[i + 1], nums[high] = nums[high], nums[i + 1]
    return i + 1


# 快速排序函数
def quickSort(nums: List, low: int, high: int):
    """
    :param arr: 排序数组
    :param low: 起始索引
    :param high: 结束索引
    :return: None -- sort in-place
    """
    if low < high:
        pi = partition(nums, low, high)

        quickSort(nums, low, pi - 1)
        quickSort(nums, pi + 1, high)


if __name__ == '__main__':
    t = [3, 1, 5, -6, 7, 12, 2, 9, 10]
    n = len(t)
    quickSort(t, 0, n-1)
    print(t)
